<!--
 * @Author: zengwj
 * @Date: 2021-09-23 14:55:47
 * @LastEditors: zengwj
 * @LastEditTime: 2021-09-23 15:46:07
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // var combinationSum = function (candidates, target) {
      //   const result = [];
      //   const path = [];
      //   backtracking(candidates, target, 0);
      //   function backtracking(candidates, target, sum) {
      //     if (sum >= target) {
      //       if (sum === target) {
      //         console.log(sum);
      //         result.push([...path]);
      //       }
      //       return;
      //     }
      //     for (let i = 0; i < candidates.length; i++) {
      //       sum += candidates[i];
      //       path.push(candidates[i]);
      //       backtracking(candidates, target, sum);
      //       sum -= candidates[i];
      //       path.pop();
      //     }
      //   }
      //   return result;
      // };
      // 牛逼
      var combinationSum = function (candidates, target) {
        const ans = [];
        const dfs = (target, combine, idx) => {
          if (idx === candidates.length) {
            return;
          }
          if (target === 0) {
            ans.push(combine);
            return;
          }
          // 直接跳过
          dfs(target, combine, idx + 1);
          // 选择当前数
          if (target - candidates[idx] >= 0) {
            dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
          }
        };

        dfs(target, [], 0);
        return ans;
      };
      console.log(combinationSum([2, 3, 6, 7], 7));
    </script>
  </body>
</html>
